#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0)); // 0,1,2,3 op times
        dp[0][0] = -prices[0];
        dp[0][1] = INT_MIN;
        dp[0][2] = INT_MIN;
        dp[0][3] = INT_MIN;
        for (int i = 1; i < prices.size(); i++)
        {
            // op0
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            // op1
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
            // op2
            if (dp[i - 1][1] != INT_MIN)
                dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);
            else
                dp[i][2] = INT_MIN;
            // op3
            if (dp[i - 1][2] != INT_MIN)
                dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);
            else
                dp[i][3] = INT_MIN;
        }
        int max = *max_element(dp[prices.size() - 1].begin(), dp[prices.size() - 1].end());
        return max < 0 ? 0 : max;
    }
};
int main()
{
    cout << "Code123" << endl;
    Solution s;
    vector<int> prices = {1};
    cout << s.maxProfit(prices) << endl;
    return 0;
}